package math

func superPow(a int, b []int) int {

	var dfs func(a, mod int, b []int) int
	dfs = func(a, mod int, b []int) int {
		if len(b) == 0 || a == 1 {
			return 1
		}

		// 第一个quickPow是b的个位数次幂    t1
		// 第二个是[a/10] int(b/10)的10次幂 t2
		// t1 * t2 = a^b
		// 举例 99^234
		// 第一个 quickPow(99,4,mod) 99^4
		// 第二个 quickPow( dfs(99,mod,[2,3]) , 10 , mod)
		// dfs求得是99^23，等效于quickPow(99^23,10,mod)，即99^230
		return quickPow(a, b[len(b)-1], mod) * quickPow(dfs(a, mod, b[:len(b)-1]), 10, mod) % mod
	}

	mod := 1337
	a %= mod
	return dfs(a, mod, b)

}

// 快速幂
func quickPow(a, b, mod int) int {

	var res int

	if a == 0 || a == 1 || b == 1 {
		return a
	}

	if b == 0 {
		return 1
	}

	if b%2 == 0 {
		temp := quickPow(a, b/2, mod) % mod
		res = temp * temp
	} else {
		res = a * quickPow(a, b-1, mod) % mod
	}

	return res

}
